Tương tự như với bậc O-lớn, nếu như tìm được các hằng số C , k 1 , k 2 {\displaystyle C,k_{1},k_{2}} đều dương và không phụ thuộc vào n {\displaystyle n} , sao cho với n {\displaystyle n} đủ lớn, các hàm R ( n ) , f ( n ) {\displaystyle R(n),f(n)} và h ( n ) {\displaystyle h(n)} đều dương và

R ( n ) ≥ C ⋅ f ( n ) {\displaystyle R(n)\geq C\cdot f(n)} k 1 ⋅ h ( n ) ≤ R ( n ) ≤ k 2 ⋅ h ( n ) {\displaystyle k_{1}\cdot h(n)\leq R(n)\leq k_{2}\cdot h(n)}

thì ta nói thuật toán có độ phức tạp cỡ lớn hơn Ω ( f ( n ) ) {\displaystyle \Omega (f(n))} , và đúng bằng cỡ Θ ( h ( n ) ) {\displaystyle \Theta (h(n))} .

Như vậy nếu xét một cách chặt chẽ, ký hiệu Θ mới biểu thị độ phức tạp của thuật toán một cách chặt chẽ. Tuy nhiên qua một thời gian dài ký hiệu O ( n ) {\displaystyle O(n)} cũng đã được dùng phổ biến, chẳng hạn [1].